//
// Created by Lantz on 2024/3/16.
//
#include <stdio.h>
#include <stdlib.h>

typedef int Elem;
typedef struct Node{
    Elem data;
    struct Node * next;
}LNode, *LinkNode;

// 初始化
bool InitList16(LinkNode &L){
    L = (LinkNode) malloc(sizeof(Node));
    L->next = NULL;
    return true;
}

// 头插法
LinkNode HeadInsert16(LinkNode &L){
    LNode * p;
    int x;
    L = (LinkNode) malloc(sizeof(Node)); // 新节点
    L->next = NULL; // 初始化为空
    scanf("%d", &x);
    while (x != 9999){
        p = (LinkNode) malloc(sizeof(Node));
        p->data = x;
        p->next = L->next;
        L->next = p;
        scanf("%d", &x);
    }
    return L;

}

// 尾插法
LinkNode TailInsert16(LinkNode &L){
    int x;
    L = (LinkNode) malloc(sizeof(Node)); // 新节点
    LNode * p, * r = L;
    scanf("%d", &x);
    while (x != 9999){
        p = (LinkNode) malloc(sizeof(Node));
        p->data = x;
        r->next = p;
        r = p;
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;

}

// 插入
bool InsertElem16(LinkNode &L, int i, Elem x){
    LNode * p = L, *s;
    int j = 0;
    while (p != NULL && j < i-1){
        p = p->next;
        j++;
    }
    s = (LinkNode) malloc(sizeof(Node));
    s->data = x;
    s->next = p->next;
    p->next = s;
    return true;
}

// 删除---要找到被删除结点的前驱
bool DeleteElem16(LinkNode &L, int i, Elem &x){
    LNode *p = L, *q;
    int j = 0;
    while (p->next != NULL && j < i-1){
        p = p->next;
        j++;
    }
    if(p->next == NULL || j > i-1){
        return false;
    }
    q = p->next;
    x = q->data;
    p->next = q->next;
    free(q);
    q = NULL;
    return true;
}

// 打印
void traverlist(LinkNode L){
    LNode * p = L->next;
    while (p != NULL){
        printf("%d ", p->data);
        p = p->next;
//        if(p != NULL){
//            printf(" ");
//        }
    }
    printf("\n");
}

int main(void){
    LinkNode L;
    Elem val;
    InitList16(L);
//    HeadInsert16(L);
//    traverlist(L);
    TailInsert16(L); // 3 4 5 6 7 8 9999
    traverlist(L);
    InsertElem16(L, 3, 33);
    traverlist(L);
    bool ret;
    ret = DeleteElem16(L, 9, val);
    if(ret){
        printf("Delete element success!\n");
        traverlist(L);
        printf("The element is %d\n", val);
    } else {
        printf("Delete element failed!\n");
    }

    return 0;
}